package org.basic.algorithm.simple;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 获取给定数组(nums)中两数之和为给定值(target)的下标
 * <p>
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那 两个 整数，并返回它们的数组下标。
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
 * 你可以按任意顺序返回答案。
 * <p>
 * 示例 1：
 * 输入：nums = [2, 7, 11, 15], target = 9
 * 输出：[0,1]
 * <p>
 * 示例 2：
 * 输入：nums = [3, 2, 4], target = 6
 * 输出：[1,2]
 * <p>
 * 示例 3：
 * 输入：nums = [3, 3], target = 6
 * 输出：[0,1]
 * <p>
 * 提示：
 * 2 <= nums.length <= 104
 * -109 <= nums[i] && target <= 109
 *
 * @author LiKun
 * @date 2021/10/8 11:14
 */
public class TwoSumOfNumber {
    /**
     * 结论：尽量不要使用双重循环寻找数据(使用HashSet)；以空间换时间；
     *
     * @param args 相关参数
     */
    public static void main(String[] args) {
        System.out.println(Arrays.toString(getArrayIndexOptimizeHashMap(new int[]{3, 2, 4}, 6)));
    }

    /**
     * 速度较慢，内存占用一般
     * 时间：55-57 ms；内存：38.3-38.9 MB
     *
     * @param nums   给定数组
     * @param target 指定值
     *
     * @return 参数下标
     */
    public static int[] getArrayIndex(int[] nums, int target) {
        // 可能需要遍历 n * (n-1) 次
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }

        return new int[]{0, 1};
    }

    /**
     * 速度较快，内存占用一般
     * 时间：2 ms；内存：38.4-38.9 MB
     *
     * @param nums   给定数组
     * @param target 指定值
     *
     * @return 参数下标
     */
    public static int[] getArrayIndexOptimizeHashMap(int[] nums, int target) {
        Integer value;
        Map<Integer, Integer> hashMap = new HashMap<>(nums.length);

        // 最多只需要遍历 nums.length 次
        for (int i = 0; i < nums.length; i++) {
            value = target - nums[i];

            if (hashMap.containsKey(value)) {
                return new int[]{i, hashMap.get(value)};
            } else {
                hashMap.put(nums[i], i);
            }
        }

        return null;
    }
}
